public class 有序数组的平方 {
    //双指针
    //时间复杂度O(n)
    //空间复杂度O(1)
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int[] answer = new int[nums.length];
            for (int i = 0, j = nums.length - 1, pos = nums.length - 1; i <= j;) {
                if (nums[i] * nums[i] > nums[j] * nums[j]) {
                    answer[pos] = nums[i] * nums[i];
                    ++i;
                } else {
                    answer[pos] = nums[j] * nums[j];
                    --j;
                }
                --pos;
            }
            return answer;
        }
    }

    //for循环 直接排序
    //时间复杂度O(logn) n为数组长度
    //空间复杂度O(logn) 排序需要空间
    // class Solution {
    //     public int[] sortedSquares(int[] nums) {
    //         for ( int i = 0; i < nums.length; i++){
    //             nums[i] = nums[i] * nums [i];
    //         }
    //         Arrays.sort(nums);
    //         return nums;
    //     }
    // }
}
